home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / DCLAP 6d / dclap6d / SeqPups / appsrc / drawtree.src / drawtree.c < prev    next >
C/C++ Source or Header  |  1996-07-05  |  31KB  |  1,210 lines
  1. #include "drawgraphics.h"
  2.  
  3. /* Version 3.52c.  Copyright (c) 1986-1993 by Joseph Felsenstein and
  4.   Christopher A. Meacham.  Additional code written by Hisashi Horino,
  5.   Sean Lamont, Andrew Keefe, and Akiko Fuseki.
  6.   Permission is granted to copy, distribute,
  7.   and modify this program provided that (1) this copyright message is
  8.   not removed and (2) no fee is charged for this program. */
  9.  
  10. #define maxnch          30
  11. #define point           '.'
  12. #define fontsize        3800
  13. #define pi              3.141592653
  14. #define epsilon         0.00001
  15. #define xstart          10
  16. #define ystart          35
  17. #define gap             0.5
  18. #define iterations      5
  19.  
  20. #ifdef MAC
  21. #undef maxnodes
  22. #define maxnodes 250
  23. #endif
  24.  
  25. typedef enum {  fixed, radial, along} labelorient;
  26. FILE *treefile, *plotfile;
  27. char        pltfilename[100];
  28. long        ntips, nextnode,  strpwide, strpdeep,
  29.         strptop, strpbottom,  payge, numlines;
  30. double       xmargin, ymargin, topoflabels, rightoflabels, leftoflabels,
  31.               bottomoflabels, ark, maxx, maxy, minx, miny, scale, xscale,
  32.           yscale, xoffset, yoffset, charht, xnow, ynow, xunitspercm,
  33.           yunitspercm, xsize, ysize, xcorner, ycorner,labelheight,
  34.           labelrotation, treeangle,  expand, bscale,enthusiasm;
  35. boolean        canbeplotted, preview, previewing, dotmatrix,haslengths,
  36.            uselengths, regular, didreroot, rotate, empty, rescaled,
  37.                notfirst, improve;
  38.        double textlength[maxnodes], firstlet[maxnodes];
  39.        striptype stripe;
  40.        plottertype plotter, oldplotter, previewer;
  41.        growth grows;
  42.        labelorient labeldirec;
  43.        node *root, *where;
  44.       node *nodep[maxnodes];
  45.        fonttype font;
  46.        enum {  yes, no } penchange, oldpenchange;
  47. char ch;
  48. char fontname[64];
  49. long filesize;
  50. long strpdiv;
  51.  
  52. openfile(fp,filename,mode,application,perm)
  53. FILE **fp;
  54. char *filename;
  55. char *mode;
  56. char *application;
  57. char *perm;
  58. {
  59.   FILE *of;
  60.   char file[100];
  61.   strcpy(file,filename);
  62.   while (1){
  63.     of = fopen(file,mode);
  64.     if (of)
  65.       break;
  66.     else {
  67.       switch (*mode){
  68.       case 'r':
  69.         printf("%s:  can't read %s\n",application,file);
  70.         file[0]='\0';
  71.         while (file[0] =='\0'){
  72.           printf("Please enter a new filename>");
  73.           gets(file);}
  74.         break;
  75.       case 'w':
  76.         printf("%s: can't write %s\n",application,file);
  77.         file[0] = '\0';
  78.         while (file[0] =='\0'){
  79.           printf("Please enter a new filename>");
  80.           gets(file);}
  81.         break;
  82.       }
  83.     }
  84.   }
  85.   *fp=of;
  86.   if (perm != NULL)
  87.     strcpy(perm,file);
  88. }
  89.  
  90. void uppercase(ch)
  91. Char *ch;
  92. {
  93.   /* make ch upper-case */
  94.    *ch = (islower(*ch) ?  toupper(*ch) : (*ch));
  95. }  /* uppercase */
  96.  
  97. /* Local variables for treeread: */
  98.  
  99. void getch(c)
  100. Char *c;
  101. {
  102.   /* get next nonblank character */
  103.   do {*c = getc(treefile);
  104.   } while ((*c == ' ')||(*c == '\n')||(*c == '\t'));
  105. }  /* getch */
  106.  
  107. void processlength(p)
  108. node *p;
  109. {
  110.   long  digit, ordzero;
  111.   double valyew, divisor;
  112.   boolean pointread, minusread;
  113.  
  114.   ordzero = '0';
  115.   pointread = false;
  116.   minusread = false;
  117.   valyew = 0.0;
  118.   divisor = 1.0;
  119.   getch(&ch);
  120.   digit = ch - ordzero;
  121.   while (((unsigned long)digit <= 9) || (ch == '.') || (ch == '.')){
  122.         if (ch == '.')   pointread = true;
  123.    else if (ch == '-')   minusread = true;
  124.    else {
  125.         valyew = valyew * 10.0 + digit;
  126.         if (pointread)
  127.           divisor *= 10.0;
  128.       }
  129.         getch(&ch);
  130.         digit = ch - ordzero;
  131.       }
  132.  if (!minusread)
  133.    p->oldlen = valyew / divisor;
  134.  else
  135.    p->oldlen = 0.0;
  136.   /* processlength */
  137. }
  138.  
  139. void addelement(p, q)
  140. node **p, *q;
  141. {
  142.   /* read in and add next part of tree, it will be node p
  143.     and will be hooked to pointer q */
  144.   node *pp;
  145.   long n,indx;
  146.   boolean notlast;
  147.  
  148.   nextnode++;
  149.   *p = (node *)Malloc((long)sizeof(node));
  150.   nodep[nextnode - 1] = *p;
  151.   indx = nextnode;
  152.   (*p)->index = indx;
  153.   if (ch == '(') {
  154.     (*p)->tip = false;
  155.     pp = *p;
  156.     notlast = true;
  157.     while (notlast) {
  158.       pp->next = (node *)Malloc((long)sizeof(node));
  159.       pp->next->tip = false;
  160.       nextnode++;
  161.       nodep[nextnode - 1] = pp->next;
  162.       pp->next->index = indx;
  163.       pp = pp->next;
  164.       getch(&ch);
  165.       addelement(&pp->back, pp);
  166.       if (ch == ')') {
  167.     notlast = false;
  168.     do {
  169.       getch(&ch);
  170.     } while (ch != ':' && ch != ',' && ch != ')' && ch != '[' &&
  171.          ch != ';');
  172.       }
  173.     }
  174.     pp->next = *p;
  175.   } else {
  176.     (*p)->tip = true;
  177.     ntips++;
  178.     n = 1;
  179.     do {
  180.       if (!ebcdic && (ch & 255) == 255)
  181.     ch = '\'';
  182.       if (!ebcdic && (ch & 255) > 175)
  183.     ch -= 48;
  184.       if (!ebcdic && (ch & (~127)) != 0)
  185.     ch -= 64;
  186.       if (ch == '_')
  187.     ch = ' ';
  188.       if (n < maxnch)
  189.     (*p)->nayme[n - 1] = ch;
  190.       if (eoln(treefile)) {
  191.     fscanf(treefile, "%*[^\n]");
  192.     (void)getc(treefile);
  193.       }
  194.       ch = getc(treefile);
  195.       if (ch == '\n')
  196.     ch = ' ';
  197.       n++;
  198.     } while (ch != ':' && ch != ',' && ch != ')');
  199.     if (n > maxnch)
  200.       n = maxnch + 1;
  201.     (*p)->naymlength = n - 1;
  202.   }
  203.   if (ch == ':')
  204.     processlength(*p);
  205.   else
  206.     haslengths = (haslengths && q == NULL);
  207.   (*p)->back = q;
  208.   if (haslengths && q != NULL)
  209.     (*p)->back->oldlen = (*p)->oldlen;
  210.   (*p)->r = 0.0;
  211.   (*p)->theta = 0.0;
  212. }  /* addelement */
  213.  
  214. void treeread()
  215. {
  216.   /* read a tree from the treefile and set up nodes and pointers */
  217.   haslengths = true;
  218.   ntips = 0;
  219.   nextnode = 0;
  220.   getch(&ch);
  221.   addelement(&root, NULL);
  222.   root->oldlen = 0.0;
  223.   fscanf(treefile, "%*[^\n]");
  224.   (void)getc(treefile);
  225.   uselengths = haslengths;
  226.   where = root;
  227.   rotate = true;
  228. }  /* treeread */
  229.  
  230. void initialparms()
  231. {
  232.   /* initialize parameters */
  233.  
  234.   getplotter();
  235.   plotrparms();
  236.   xmargin = 0.08 * xsize;
  237.   ymargin = 0.08 * ysize;
  238.   xscale = xunitspercm;
  239.   yscale = yunitspercm;
  240.   grows = vertical;
  241.   treeangle = pi / 2.0;
  242.   ark = 2 * pi;
  243.   improve = true;
  244.   regular = false;
  245.   rescaled = true;
  246.   bscale = 1.0;
  247.   labeldirec = fixed;
  248.   labelrotation = 0.0;
  249.   charht = 0.3333;
  250.   numlines = dotmatrix ? ((long)floor(yunitspercm * ysize + 0.5) / strpdeep):1;
  251.   enthusiasm = 1.0/(double)ntips;
  252. }  /* initialparms */
  253.  
  254.  
  255. long showparms()
  256. {
  257.   long i;
  258.   long numtochange;
  259.   Char ch,input[64];
  260.   double treea;
  261.  
  262.   putchar('\n');
  263.   if (previewer == tek)
  264.     printf("%c\f", escape);
  265.   else {
  266.     for (i = 1; i <= 24; i++)
  267.       putchar('\n');
  268.   }
  269.   printf("Here are the settings: \n\n");
  270.   printf(" (1)        Use branch lengths:  ");
  271.   if (haslengths)
  272.     printf("%s\n",uselengths ? "Yes" : "No");
  273.    else
  274.     printf("(no branch lengths available)\n");
  275.   printf(" (2)           Angle of labels:");
  276.   if (labeldirec == fixed) {
  277.     printf("  Fixed angle of");
  278.     if (labelrotation >= 10.0)
  279.       printf("%6.1f", labelrotation);
  280.     else if (labelrotation <= -10.0)
  281.       printf("%7.1f", labelrotation);
  282.     else if (labelrotation < 0.0)
  283.       printf("%6.1f", labelrotation);
  284.     else
  285.       printf("%5.1f", labelrotation);
  286.     printf(" degrees\n");
  287.   } else if (labeldirec == radial)
  288.     printf("  Radial\n");
  289.   else
  290.     printf("  Along branches\n");
  291.   printf(" (3)          Rotation of tree:");
  292.   treea = treeangle * 180 / pi;
  293.   if (treea >= 100.0)
  294.     printf("%7.1f\n", treea);
  295.   else if (treea >= 10.0)
  296.     printf("%6.1f\n", treea);
  297.   else if (treea <= -100.0)
  298.     printf("%8.1f\n", treea);
  299.   else if (treea <= -10.0)
  300.     printf("%7.1f\n", treea);
  301.   else if (treea < 0.0)
  302.     printf("%6.1f\n", treea);
  303.   else
  304.     printf("%5.1f\n", treea);
  305.   printf(" (4)     Angle of arc for tree:");
  306.   treea = 180 * ark / pi;
  307.   if (treea >= 100.0)
  308.     printf("%7.1f\n", treea);
  309.   else if (treea >= 10.0)
  310.     printf("%6.1f\n", treea);
  311.   else if (treea <= -100.0)
  312.     printf("%8.1f\n", treea);
  313.   else if (treea <= -10.0)
  314.     printf("%7.1f\n", treea);
  315.   else if (treea < 0.0)
  316.     printf("%6.1f\n", treea);
  317.   else
  318.     printf("%5.1f\n", treea);
  319.   printf(" (5)   Iterate to improve tree:  %s\n",
  320.      (improve ? "Yes" : "No"));
  321.   printf(" (6)    Scale of branch length:");
  322.   if (rescaled)
  323.     printf("  Automatically rescaled\n");
  324.   else
  325.     printf("  Fixed:%6.2f cm per unit branch length\n", bscale);
  326.   didreroot = false;
  327.   printf(" (7)        Horizontal margins:%6.2f cm\n", xmargin);
  328.   printf(" (7)          Vertical margins:%6.2f cm\n", ymargin);
  329.   printf(" (8) Relative character height:%8.4f\n", charht);
  330.   if (!improve)
  331.     printf(" (9)     Regularize the angles:  %s\n",(regular ? "Yes" : "No"));
  332.   else
  333.     printf(" (9)       Enthusiasm constant:%9.5f\n",enthusiasm);
  334.   if (plotter == lw)
  335.     printf(" (10)           Font          :  %s\n",fontname);
  336.  
  337.   printf("\n\n Do you want to accept these? (Yes or No)\n");
  338.   for (;;) {
  339.     printf(" Type Y or N or the number (1-%2ld) of the one to change: \n",
  340.             (plotter == lw) ? 10L : 9L);
  341.     gets(input);
  342.     uppercase(&input[0]);
  343.     ch=input[0];
  344.     numtochange = atoi(input);
  345.     if ((ch == 'Y' || ch == 'N') || (numtochange >= 1 && numtochange <=
  346.        ((plotter == lw) ? 10 : 9)))
  347.       break;
  348.   }
  349.   return (ch == 'Y') ? -1 : numtochange;
  350. }  /* showparms */
  351.  
  352. void rerootit(p)
  353. node *p;
  354. {
  355.   node *q;
  356.  
  357.   q = root;
  358.   while (q->next != root)
  359.     q = q->next;
  360.   q->next = root->next;
  361.   q = p;
  362.   while (q->next != p)
  363.     q = q->next;
  364.   root->next = p;
  365.   q->next = root;
  366. }  /* rerootit */
  367.  
  368. void reroot()
  369. {
  370.   /* reroot the tree, traversing tree */
  371.   where = root->next;
  372.   if (!rotate)
  373.     rotate = where->back->tip;
  374.   if (rotate) {
  375.     where = where->next;
  376.     rotate = false;
  377.   } else {
  378.     where = where->back;
  379.     rotate = true;
  380.   }
  381.   rerootit(where);
  382. }  /* reroot */
  383.  
  384.  
  385. void getparms(numtochange)
  386. long numtochange;
  387. {
  388.   /* get from user the relevant parameters for the plotter and diagram */
  389.   Char ch;
  390.   boolean ok;
  391.  
  392.   if (numtochange == 0) {
  393.     do {
  394.       printf(" Type the number of one that you want to change (1-%2ld):\n",
  395.               (plotter == lw) ? 10L : 9L);
  396.       scanf("%ld%*[^\n]", &numtochange);
  397.       (void)getchar();
  398.     } while (numtochange < 1 || numtochange > ((plotter == lw) ? 10 : 9));
  399.   }
  400.   switch (numtochange) {
  401.  
  402.   case 1:
  403.     if (haslengths)
  404.       uselengths = !uselengths;
  405.     else {
  406.       printf("Cannot use lengths since not all of them exist\n");
  407.       uselengths = false;
  408.     }
  409.     break;
  410.  
  411.   case 2:
  412.     printf("\nDo you want labels to be Fixed angle, Radial,");
  413.     printf(" or Along branches?\n");
  414.     do {
  415.       printf(" Type F, R, or A\n");
  416.       scanf("%c%*[^\n]", &ch);
  417.       (void)getchar();
  418.       if (ch == '\n')
  419.     ch = ' ';
  420.       uppercase(&ch);
  421.     } while (ch != 'F' && ch != 'R' && ch != 'A');
  422.     switch (ch) {
  423.  
  424.     case 'A':
  425.       labeldirec = along;
  426.       break;
  427.  
  428.     case 'F':
  429.       labeldirec = fixed;
  430.       break;
  431.  
  432.     case 'R':
  433.       labeldirec = radial;
  434.       break;
  435.     }
  436.     if (labeldirec == fixed) {
  437.       printf("Are the labels to be plotted vertically (90),\n");
  438.       printf(" horizontally (0), or downwards (-90) ?\n");
  439.       do {
  440.     printf(" Choose an angle in degrees from 90 to -90: \n");
  441.     scanf("%lf%*[^\n]", &labelrotation);
  442.     (void)getchar();
  443.       } while ((labelrotation < -90.0 || labelrotation > 90.0) &&
  444.            labelrotation != -99.0);
  445.     }
  446.     break;
  447.  
  448.   case 3:
  449.     printf("\n At what angle is the tree to be plotted?\n");
  450.     do {
  451.       printf(" Choose an angle in degrees from 360 to -360: \n");
  452.       scanf("%lf%*[^\n]", &treeangle);
  453.       (void)getchar();
  454.       uppercase(&ch);
  455.     } while (treeangle < -360.0 && treeangle > 360.0);
  456.     treeangle = treeangle * pi / 180;
  457.     break;
  458.  
  459.   case 4:
  460.     printf(" How many degrees (up to 360) of arc\n");
  461.     printf("  should the tree occupy? (Currently it is %5.1f)\n",
  462.        180 * ark / pi);
  463.     do {
  464.       printf("Enter a number of degrees from 0 up to 360)\n");
  465.       scanf("%lf%*[^\n]", &ark);
  466.       (void)getchar();
  467.     } while (ark <= 0.0 || ark > 360.0);
  468.     ark = ark * pi / 180;
  469.     break;
  470.  
  471.   case 5:
  472.     improve = !improve;
  473.     break;
  474.  
  475.   case 6:
  476.     rescaled = !rescaled;
  477.     if (!rescaled) {
  478.       printf("Centimeters per unit branch length?\n");
  479.       scanf("%lf%*[^\n]", &bscale);
  480.       (void)getchar();
  481.     }
  482.     break;
  483.  
  484.   case 7:
  485.     printf("\nThe tree will be drawn to fit in a rectangle which has \n");
  486.     printf(" margins in the horizontal and vertical directions of:\n");
  487.     printf("%6.2f cm (horizontal margin) and%6.2f cm (vertical margin)\n\n",
  488.        xmargin, ymargin);
  489.     do {
  490.       printf(" New value (in cm) of horizontal margin?\n");
  491.       scanf("%lf%*[^\n]", &xmargin);
  492.       (void)getchar();
  493.       ok = ((unsigned)xmargin < xsize / 2.0);
  494.       if (!ok)
  495.     printf(" Impossible value.  Please retype it.\n");
  496.     } while (!ok);
  497.     do {
  498.       printf(" New value (in cm) of vertical margin?\n");
  499.       scanf("%lf%*[^\n]", &ymargin);
  500.       (void)getchar();
  501.       ok = ((unsigned)ymargin < ysize / 2.0);
  502.       if (!ok)
  503.     printf(" Impossible value.  Please retype it.\n");
  504.     } while (!ok);
  505.     break;
  506.  
  507.   case 8:
  508.     printf("New value of character height?\n");
  509.     scanf("%lf%*[^\n]", &charht);
  510.     (void)getchar();
  511.     break;
  512.   case 9:
  513.     if (improve) {
  514.       do {
  515.     printf("Enthusiasm constant? (must be between 0 and 1)\n");
  516.     scanf("%lf%*[^\n]", &enthusiasm);
  517.     getchar();
  518.       } while (enthusiasm <= 0.0 || enthusiasm > 1.0);}
  519.     else
  520.       regular = !regular;
  521.     break;
  522.   case 10:
  523.     printf("Enter font name or \"Hershey\" for default font\n");
  524.     gets(fontname);
  525.     break;
  526.   }
  527. }  /* getparms */
  528.  
  529.  
  530. Local void getwidth(p)
  531. node *p;
  532. {
  533.   /* get width and depth beyond each node */
  534.   double nw, nd;
  535.   node *pp, *qq;
  536.  
  537.   nd = 0.0;
  538.   if (p->tip)
  539.     nw = 1.0;
  540.   else {
  541.     nw = 0.0;
  542.     qq = p;
  543.     pp = p->next;
  544.     do {
  545.       getwidth(pp->back);
  546.       nw += pp->back->width;
  547.       if (pp->back->depth > nd)
  548.     nd = pp->back->depth;
  549.       pp = pp->next;
  550.     } while (pp != qq);
  551.   }
  552.   p->depth = nd + p->length;
  553.   p->width = nw;
  554. }  /* getwidth */
  555.  
  556. void plrtrans(p, theta, lower, upper)
  557. node *p;
  558. double theta, lower, upper;
  559. {
  560.   /* polar coordinates of a node relative to start */
  561.   long num;
  562.   double nn, pr, ptheta, angle, angle2, subangle, len;
  563.   node *pp, *qq;
  564.  
  565.   nn = p->width;
  566.   angle = theta;
  567.   subangle = (upper - lower) / nn;
  568.   qq = p;
  569.   pp = p->next;
  570.   if (p->tip)
  571.     return;
  572.   angle = upper;
  573.   do {
  574.     angle -= pp->back->width / 2.0 * subangle;
  575.     pr = p->r;
  576.     ptheta = p->theta;
  577.     if (regular) {
  578.       num = 1;
  579.       while (num * subangle < 2 * pi)
  580.     num *= 2;
  581.       if (angle >= 0.0)
  582.     angle2 = 2 * pi / num * (long)(num * angle / (2 * pi) + 0.5);
  583.       else
  584.     angle2 = 2 * pi / num * (long)(num * angle / (2 * pi) - 0.5);
  585.     } else
  586.       angle2 = angle;
  587.     if (uselengths)
  588.       len = pp->back->oldlen;
  589.     else
  590.       len = 1.0;
  591.     pp->back->r = sqrt(len * len + pr * pr + 2 * len * pr * cos(angle2 - ptheta));
  592.     if (fabs(pr * cos(ptheta) + len * cos(angle2)) > epsilon)
  593.       pp->back->theta = atan((pr * sin(ptheta) + len * sin(angle2)) /
  594.                  (pr * cos(ptheta) + len * cos(angle2)));
  595.     else if (pr * sin(ptheta) + len * sin(angle2) >= 0.0)
  596.       pp->back->theta = pi / 2;
  597.     else
  598.       pp->back->theta = 1.5 * pi;
  599.     if (pr * cos(ptheta) + len * cos(angle2) < -epsilon)
  600.       pp->back->theta += pi;
  601.     if (!pp->back->tip)
  602.       plrtrans(pp->back, pp->back->theta,
  603.          angle - pp->back->width * subangle / 2.0,
  604.          angle + pp->back->width * subangle / 2.0);
  605.     else
  606.       pp->back->oldtheta = angle2;
  607.     angle -= pp->back->width / 2.0 * subangle;
  608.     pp = pp->next;
  609.   } while (pp != qq);
  610. }  /* plrtrans */
  611.  
  612. void coordtrav(p, xx, yy)
  613. node *p;
  614. double *xx, *yy;
  615. {
  616.   /* compute x and y coordinates */
  617.   long i;
  618.   node *pp;
  619.  
  620.   if (!p->tip) {
  621.     pp = p->next;
  622.     while (pp != p) {
  623.       coordtrav(pp->back, xx,yy);
  624.       pp = pp->next;
  625.     }
  626.   }
  627.   if (p->tip) {
  628.     i = 1;
  629.     while (nodep[i - 1] != p)
  630.       i++;
  631.     textlength[i - 1] = (double)lengthtext(p->nayme, p->naymlength, font);
  632.   }
  633.   (*xx) = p->r * cos(p->theta);
  634.   (*yy) = p->r * sin(p->theta);
  635.   if ((*xx) > maxx)
  636.     maxx = (*xx);
  637.   if ((*xx) < minx)
  638.     minx = (*xx);
  639.   if ((*yy) > maxy)
  640.     maxy = (*yy);
  641.   if ((*yy) < miny)
  642.     miny = (*yy);
  643.   p->xcoord = (*xx);
  644.   p->ycoord = (*yy);
  645. }  /* coordtrav */
  646.  
  647.  
  648. double angleof(x, y)
  649. double x, y;
  650. {
  651.   /* compute the angle of a vector */
  652.   double theta;
  653.  
  654.   if (fabs(x) > epsilon)
  655.     theta = atan(y / x);
  656.   else if (y >= 0.0)
  657.     theta = pi / 2;
  658.   else
  659.     theta = 1.5 * pi;
  660.   if (x < -epsilon)
  661.     theta = pi + theta;
  662.   if (theta > 2 * pi)
  663.     theta -= 2 * pi;
  664.   return theta;
  665. }  /* angleof */
  666.  
  667. void polartrav(p,xx,yy,leftx,lefty,rightx,righty)
  668. node    *p;
  669. double  *xx,*yy,*leftx,*lefty,*rightx,*righty;
  670. {
  671.   /* go through subtree getting left and right vectors */
  672.   double x, y;
  673.   boolean lookatit;
  674.   node *pp;
  675.  
  676.   lookatit = true;
  677.   if (!p->tip)
  678.     lookatit = (p->next->next->next != p || p->index != root->index);
  679.   if (lookatit) {
  680.     x = nodep[p->index - 1]->xcoord;
  681.     y = nodep[p->index - 1]->ycoord;
  682.     if ((y - (*yy)) * (*rightx) - (x - (*xx)) * (*righty) < 0.0) {
  683.       (*rightx) = x - (*xx);
  684.       (*righty) = y - (*yy);
  685.     }
  686.     if ((y - (*yy)) * (*leftx) - (x - (*xx)) * (*lefty) > 0.0 &&
  687.     !(notfirst && fabs((*rightx) - x + (*xx)) +
  688.       fabs((*righty) - y + (*yy)) < epsilon)) {
  689.       (*leftx) = x - (*xx);
  690.       (*lefty) = y - (*yy);
  691.       notfirst = true;
  692.     }
  693.   }
  694.   if (p->tip)
  695.     return;
  696.   pp = p->next;
  697.   while (pp != p) {
  698.     if (pp != root)
  699.       polartrav(pp->back,xx,yy,leftx,lefty,rightx,righty);
  700.     pp = pp->next;
  701.   }
  702. }  /* polartrav */
  703.  
  704. void tilttrav(q,xx,yy,sinphi,cosphi)
  705. node *q;
  706. double *xx,*yy,*sinphi,*cosphi;
  707. {
  708.   /* traverse to move successive nodes */
  709.   double x, y;
  710.   node *pp;
  711.  
  712.   pp = nodep[q->index - 1];
  713.   x = pp->xcoord;
  714.   y = pp->ycoord;
  715.   pp->xcoord = (*xx) + (x - (*xx)) * (*cosphi) + (y - (*yy)) * (*sinphi);
  716.   pp->ycoord = (*yy) + ((*xx) - x) * (*sinphi) + (y - (*yy)) * (*cosphi);
  717.   if (q->tip)
  718.     return;
  719.   pp = q->next;
  720.   while (pp != q) {
  721.     if (pp != root)
  722.       tilttrav(pp->back,xx,yy,sinphi,cosphi);
  723.     pp = pp->next;
  724.   }
  725. }  /* tilttrav */
  726.  
  727. void polarize(p,xx,yy)
  728. node *p;
  729. double *xx,*yy;
  730. {
  731.   double TEMP, TEMP1;
  732.  
  733.   if (fabs(p->xcoord - (*xx)) > epsilon)
  734.     p->oldtheta = atan((p->ycoord - (*yy)) / (p->xcoord - (*xx)));
  735.   else if (p->ycoord - (*yy) >= 0.0)
  736.     p->oldtheta = pi / 2;
  737.   else
  738.     p->oldtheta = 1.5 * pi;
  739.   if (p->xcoord - (*xx) < -epsilon)
  740.     p->oldtheta += pi;
  741.   if (fabs(p->xcoord - root->xcoord) > epsilon)
  742.     p->theta = atan((p->ycoord - root->ycoord) / (p->xcoord - root->xcoord));
  743.   else if (p->ycoord - root->ycoord >= 0.0)
  744.     p->theta = pi / 2;
  745.   else
  746.     p->theta = 1.5 * pi;
  747.   if (p->xcoord - root->xcoord < -epsilon)
  748.     p->theta += pi;
  749.   TEMP = p->xcoord - root->xcoord;
  750.   TEMP1 = p->ycoord - root->ycoord;
  751.   p->r = sqrt(TEMP * TEMP + TEMP1 * TEMP1);
  752. }  /* polarize */
  753.  
  754. void improvtrav(p)
  755. node *p;
  756. {
  757.   /* traverse tree trying different tiltings at each node */
  758.   double xx, yy, leftx, lefty, rightx, righty, cosphi, sinphi;
  759.   long n;
  760.   double usedangle, langle, rangle, freeangle, meanangle, sumrot;
  761.   node *pp, *qq;
  762.  
  763.   if (p->tip)
  764.     return;
  765.   xx = p->xcoord;
  766.   yy = p->ycoord;
  767.   if (p != root) {
  768.     n = 0;
  769.     usedangle = 0.0;
  770.     pp = p->next;
  771.     do {
  772.       leftx = pp->back->xcoord - xx;
  773.       lefty = pp->back->ycoord - yy;
  774.       rightx = leftx;
  775.       righty = lefty;
  776.       notfirst = false;
  777.       if (!pp->back->tip)
  778.     polartrav(pp->back, &xx,&yy,&leftx,&lefty,&rightx,&righty);
  779.       n++;
  780.       langle = angleof(leftx, lefty);
  781.       rangle = angleof(rightx, righty);
  782.       if (rangle > langle)
  783.     langle += 2 * pi;
  784.       pp->lefttheta = langle;
  785.       pp->righttheta = rangle;
  786.       usedangle += langle - rangle;
  787.       pp = pp->next;
  788.     } while (pp != p->next);
  789.     freeangle = 2 * pi - usedangle;
  790.     meanangle = freeangle / n;
  791.     sumrot = 0.0;
  792.     qq = p;
  793.     pp = p->next;
  794.     while (pp != p) {
  795.       langle = qq->righttheta;
  796.       rangle = pp->lefttheta;
  797.       if (rangle > langle)
  798.     langle += 2 * pi;
  799.       sumrot += enthusiasm * (meanangle - langle + rangle);
  800.       cosphi = cos(sumrot);
  801.       sinphi = sin(sumrot);
  802.       if (pp != root)
  803.     tilttrav(pp->back, &xx,&yy,&sinphi,&cosphi);
  804.       qq = pp;
  805.       pp = pp->next;
  806.     }
  807.   }
  808.   pp = p->next;
  809.   while (pp != p) {
  810.     if (pp != root)
  811.       polarize(pp->back, &xx,&yy);
  812.     pp = pp->next;
  813.   }
  814.   pp = p->next;
  815.   while (pp != p) {
  816.     if (pp != root)
  817.       improvtrav(pp->back);
  818.     pp = pp->next;
  819.   }
  820. }  /* improvtrav */
  821.  
  822. void coordimprov(xx,yy)
  823. double *xx,*yy;
  824. {
  825.   /* use angles calculation to improve node coordinate placement */
  826.   long i;
  827.   for (i = 1; i <= iterations; i++)
  828.     improvtrav(root);
  829. }  /* coordimprov */
  830.  
  831.  
  832. void calculate()
  833. {
  834.   /* compute coordinates for tree */
  835.   double xx, yy;
  836.   long i;
  837.   double nttot, fontheight, labangle, top, bot, rig, lef;
  838.  
  839.   for (i = 0; i < nextnode; i++)
  840.     nodep[i]->width = 1.0;
  841.   for (i = 0; i < nextnode; i++)
  842.     nodep[i]->xcoord = 0.0;
  843.   for (i = 0; i < nextnode; i++)
  844.     nodep[i]->ycoord = 0.0;
  845.   if (!uselengths) {
  846.     for (i = 0; i < nextnode; i++)
  847.       nodep[i]->length = 1.0;
  848.   } else {
  849.     for (i = 0; i < nextnode; i++)
  850.       nodep[i]->length = nodep[i]->oldlen;
  851.   }
  852.   getwidth(root);
  853.   nttot = root->width;
  854.   for (i = 0; i < nextnode; i++)
  855.     nodep[i]->width = nodep[i]->width * ntips / nttot;
  856.   plrtrans(root, treeangle, treeangle - ark / 2.0, treeangle + ark / 2.0);
  857.   maxx = 0.0;
  858.   minx = 0.0;
  859.   maxy = 0.0;
  860.   miny = 0.0;
  861.   coordtrav(root, &xx,&yy);
  862.   if (improve) {
  863.     coordimprov(&xx,&yy);
  864.     coordtrav(root, &xx,&yy);
  865.   }
  866.   fontheight = font[2];
  867.   if (labeldirec == fixed)
  868.     labangle = pi * labelrotation / 180.0;
  869.   for (i = 0; i < nextnode; i++) {
  870.     if (nodep[i]->tip)
  871.       textlength[i] /= fontheight;
  872.   }
  873.   if (ntips > 1)
  874.     labelheight = charht * (maxx - minx) / (ntips - 1);
  875.   else
  876.     labelheight = charht * (maxx - minx);
  877.   topoflabels = 0.0;
  878.   bottomoflabels = 0.0;
  879.   rightoflabels = 0.0;
  880.   leftoflabels = 0.0;
  881.   for (i = 0; i < nextnode; i++) {
  882.     if (nodep[i]->tip) {
  883.       if (labeldirec == radial)
  884.     labangle = nodep[i]->theta;
  885.       else if (labeldirec == along)
  886.     labangle = nodep[i]->oldtheta;
  887.       if (cos(labangle) < 0.0 && labeldirec != fixed)
  888.     labangle -= pi;
  889.       firstlet[i] = (double)lengthtext(nodep[i]->nayme,1L,font)/ fontheight;
  890.       top = (nodep[i]->ycoord - maxy) / labelheight + sin(nodep[i]->oldtheta);
  891.       rig = (nodep[i]->xcoord - maxx) / labelheight + cos(nodep[i]->oldtheta);
  892.       bot = (miny - nodep[i]->ycoord) / labelheight - sin(nodep[i]->oldtheta);
  893.       lef = (minx - nodep[i]->xcoord) / labelheight - cos(nodep[i]->oldtheta);
  894.       if (cos(labangle) * cos(nodep[i]->oldtheta) +
  895.       sin(labangle) * sin(nodep[i]->oldtheta) > 0.0) {
  896.     if (sin(labangle) > 0.0)
  897.       top += sin(labangle) * textlength[i];
  898.     top += sin(labangle - 1.25 * pi) * gap * firstlet[i];
  899.     if (sin(labangle) < 0.0)
  900.       bot -= sin(labangle) * textlength[i];
  901.     bot -= sin(labangle - 0.75 * pi) * gap * firstlet[i];
  902.     if (sin(labangle) > 0.0)
  903.       rig += cos(labangle - 0.75 * pi) * gap * firstlet[i];
  904.     else
  905.       rig += cos(labangle - 1.25 * pi) * gap * firstlet[i];
  906.     rig += cos(labangle) * textlength[i];
  907.     if (sin(labangle) > 0.0)
  908.       lef -= cos(labangle - 1.25 * pi) * gap * firstlet[i];
  909.     else
  910.       lef -= cos(labangle - 0.75 * pi) * gap * firstlet[i];
  911.       } else {
  912.     if (sin(labangle) < 0.0)
  913.       top -= sin(labangle) * textlength[i];
  914.     top += sin(labangle + 0.25 * pi) * gap * firstlet[i];
  915.     if (sin(labangle) > 0.0)
  916.       bot += sin(labangle) * textlength[i];
  917.     bot -= sin(labangle - 0.25 * pi) * gap * firstlet[i];
  918.     if (sin(labangle) > 0.0)
  919.       rig += cos(labangle - 0.25 * pi) * gap * firstlet[i];
  920.     else
  921.       rig += cos(labangle + 0.25 * pi) * gap * firstlet[i];
  922.     if (sin(labangle) < 0.0)
  923.       rig += cos(labangle) * textlength[i];
  924.     if (sin(labangle) > 0.0)
  925.       lef -= cos(labangle + 0.25 * pi) * gap * firstlet[i];
  926.     else
  927.       lef -= cos(labangle - 0.25 * pi) * gap * firstlet[i];
  928.     lef += cos(labangle) * textlength[i];
  929.       }
  930.       if (top > topoflabels)
  931.     topoflabels = top;
  932.       if (bot > bottomoflabels)
  933.     bottomoflabels = bot;
  934.       if (rig > rightoflabels)
  935.     rightoflabels = rig;
  936.       if (lef > leftoflabels)
  937.     leftoflabels = lef;
  938.     }
  939.   }
  940.   topoflabels *= labelheight;
  941.   bottomoflabels *= labelheight;
  942.   leftoflabels *= labelheight;
  943.   rightoflabels *= labelheight;
  944. }  /* calculate */
  945.  
  946.  
  947. void rescale()
  948. {
  949.   /* compute coordinates of tree for plot or preview device */
  950.   long i;
  951.   double treeheight, treewidth, extrax, extray, temp;
  952.  
  953.   treeheight = maxy - miny + topoflabels + bottomoflabels;
  954.   treewidth = maxx - minx + rightoflabels + leftoflabels;
  955.   if (grows == vertical) {
  956.     if (!rescaled)
  957.       expand = bscale;
  958.     else {
  959.       expand = (xsize - 2 * xmargin) / treewidth;
  960.       if ((ysize - 2 * ymargin) / treeheight < expand)
  961.     expand = (ysize - 2 * ymargin) / treeheight;
  962.     }
  963.     extrax = (xsize - 2 * xmargin - treewidth * expand) / 2.0;
  964.     extray = (ysize - 2 * ymargin - treeheight * expand) / 2.0;
  965.   } else {
  966.     if (!rescaled)
  967.       expand = bscale;
  968.     else {
  969.       expand = (ysize - 2 * ymargin) / treewidth;
  970.       if ((xsize - 2 * xmargin) / treeheight < expand)
  971.     expand = (xsize - 2 * xmargin) / treeheight;
  972.     }
  973.     extrax = (xsize - 2 * xmargin - treeheight * expand) / 2.0;
  974.     extray = (ysize - 2 * ymargin - treewidth * expand) / 2.0;
  975.   }
  976.   for (i = 0; i < (nextnode); i++) {
  977.     nodep[i]->xcoord = expand * (nodep[i]->xcoord - minx + leftoflabels);
  978.     nodep[i]->ycoord = expand * (nodep[i]->ycoord - miny + bottomoflabels);
  979.     if (grows == horizontal) {
  980.       temp = nodep[i]->ycoord;
  981.       nodep[i]->ycoord = expand * treewidth - nodep[i]->xcoord;
  982.       nodep[i]->xcoord = temp;
  983.     }
  984.     nodep[i]->xcoord += xmargin + extrax;
  985.     nodep[i]->ycoord += ymargin + extray;
  986.   }
  987. }  /* rescale */
  988.  
  989. void plottree(p, q)
  990. node *p, *q;
  991. {
  992.   /* plot part or all of tree on the plotting device */
  993.   double x1, y1, x2, y2;
  994.   node *pp;
  995.  
  996.   x2 = xscale * (xoffset + p->xcoord);
  997.   y2 = yscale * (yoffset + p->ycoord);
  998.   if (p != root) {
  999.     x1 = xscale * (xoffset + q->xcoord);
  1000.     y1 = yscale * (yoffset + q->ycoord);
  1001.     plot(penup, x1, y1);
  1002.     plot(pendown, x2, y2);
  1003.   }
  1004.   if (p->tip)
  1005.     return;
  1006.   pp = p->next;
  1007.   while (pp != p) {
  1008.     plottree(pp->back, p);
  1009.     pp = pp->next;
  1010.   }
  1011. }  /* plottree */
  1012.  
  1013.  
  1014. void plotlabels(fontname)
  1015. char *fontname;
  1016. {
  1017.   long i;
  1018.   double compr, dx, dy, labangle;
  1019.   boolean left, right;
  1020.   node *lp;
  1021.  
  1022.   compr = xunitspercm / yunitspercm;
  1023.   if (penchange == yes)
  1024.     changepen(labelpen);
  1025.   for (i = 0; i < (nextnode); i++) {
  1026.     if (nodep[i]->tip) {
  1027.       lp = nodep[i];
  1028.       labangle = labelrotation * pi / 180.0;
  1029.       if (labeldirec == radial)
  1030.     labangle = nodep[i]->theta;
  1031.       else if (labeldirec == along)
  1032.     labangle = nodep[i]->oldtheta;
  1033.       if (cos(labangle) < 0.0)
  1034.     labangle -= pi;
  1035.       right = (cos(labangle) * cos(nodep[i]->oldtheta) +
  1036.            sin(labangle) * sin(nodep[i]->oldtheta) > 0.0);
  1037.       left = !right;
  1038.       dx = labelheight * expand * cos(nodep[i]->oldtheta);
  1039.       dy = labelheight * expand * sin(nodep[i]->oldtheta);
  1040.       if (right) {
  1041.     dx += labelheight * expand * 0.5 * firstlet[i] * cos(labangle - 0.75 * pi);
  1042.     dy += labelheight * expand * 0.5 * firstlet[i] * sin(labangle - 0.75 * pi);
  1043.       }
  1044.       if (left) {
  1045.     dx += labelheight * expand * 0.5 * firstlet[i] * cos(labangle - 0.25 * pi);
  1046.     dy += labelheight * expand * 0.5 * firstlet[i] * sin(labangle - 0.25 * pi);
  1047.     dx -= textlength[i] * labelheight * expand * cos(labangle);
  1048.     dy -= textlength[i] * labelheight * expand * sin(labangle);
  1049.       }
  1050.     
  1051.       plottext(lp->nayme, lp->naymlength,
  1052.            labelheight * expand * xscale / compr, compr,
  1053.            xscale * (lp->xcoord + dx + xoffset),
  1054.            yscale * (lp->ycoord + dy + yoffset), -180 * labangle / pi,
  1055.            font,fontname);
  1056.     }
  1057.   }
  1058.   if (penchange == yes)
  1059.     changepen(treepen);
  1060. }  /* plotlabels */
  1061.  
  1062.  
  1063.  
  1064. #ifdef CHILDAPP
  1065. void RealMain(int argc, char** argv)
  1066. #else
  1067. main(argc, argv)
  1068.      int argc;
  1069.      Char *argv[];
  1070. #endif
  1071.  
  1072. {
  1073.   long i,n,stripedepth;
  1074.   char filename1[100];
  1075. #if defined(MAC) || defined(__MWERKS__)
  1076.   OSErr retcode;
  1077.   FInfo  fndrinfo;
  1078. #ifdef MAC
  1079.   macsetup("Drawtree","Preview");
  1080. #endif
  1081. #endif
  1082. #ifdef TURBOC
  1083.   if ((registerbgidriver(EGAVGA_driver) <0) ||
  1084.       (registerbgidriver(Herc_driver) <0)   ||
  1085.       (registerbgidriver(CGA_driver) <0)){
  1086.     fprintf(stderr,"Graphics error: %s ",grapherrormsg(graphresult()));
  1087.     exit(-1);}
  1088. #endif
  1089.   strcpy(fontname,"Hershey");
  1090.  
  1091.   openfile(&plotfile,PLOTFILE,"w",argv[0],pltfilename);
  1092.   openfile(&treefile,TREEFILE,"r",argv[0],NULL);
  1093.  
  1094.   printf("DRAWTREE from PHYLIP version %s\n",VERSION);
  1095.   printf("Reading tree ... \n");
  1096.   treeread();
  1097.   printf("Tree has been read.\n");
  1098.   printf("Loading the font ... \n");
  1099.   loadfont(font,argv[0]);
  1100.   printf("Font loaded.\n");
  1101.   previewing = false;
  1102.   initialparms();
  1103.  
  1104.   canbeplotted = false;
  1105.   while (!canbeplotted) {
  1106.     do {
  1107.       n=showparms();
  1108.       if ( n != -1)
  1109.     getparms(n);
  1110.     } while (n != -1);
  1111.     calculate();
  1112.     rescale();
  1113.     canbeplotted = true;
  1114.     if (preview)
  1115.       canbeplotted=plotpreview(fontname,&xoffset,&yoffset,&scale,ntips,root);
  1116.   }
  1117.   if (dotmatrix) {
  1118.      stripedepth = allocstripe(stripe,(strpwide/8),
  1119.                 ((long)(yunitspercm * ysize)));
  1120.      strpdeep = stripedepth;
  1121.      strpdiv  = stripedepth;
  1122.      }
  1123.   previewing = false;
  1124.   initplotter(ntips,fontname);
  1125.   numlines = dotmatrix ? ((long)floor(yunitspercm * ysize + 0.5)/strpdeep):1;   if (plotter != ibmpc)
  1126.     printf("Writing plot file ...\n");
  1127.   drawit(fontname,&xoffset,&yoffset,numlines,root);
  1128.   finishplotter();
  1129.   printf("Finished.\n");
  1130.   FClose(treefile);
  1131.   FClose(plotfile);
  1132.   printf("End of run.\n");
  1133.  
  1134. #ifdef MAC
  1135.   if (plotter == pict){
  1136.     strcpy(filename1,pltfilename);
  1137.     retcode=GetFInfo(CtoPstr(filename1),0,&fndrinfo);
  1138.     fndrinfo.fdType='PICT';
  1139.     fndrinfo.fdCreator='MDRW';
  1140.     strcpy(filename1,pltfilename);
  1141.     retcode=SetFInfo(CtoPstr(PLOTFILE),0,&fndrinfo);}
  1142.   if (plotter == lw){
  1143.     retcode=GetFInfo(CtoPstr(PLOTFILE),0,&fndrinfo);
  1144.     fndrinfo.fdType='TEXT';
  1145.     retcode=SetFInfo(CtoPstr(PLOTFILE),0,&fndrinfo);}
  1146. #endif
  1147. #if defined(__MWERKS__)
  1148. if (plotter == pict){
  1149.   strcpy(filename1,pltfilename);
  1150.   retcode= getfinfo( pltfilename,0,&fndrinfo);
  1151.   fndrinfo.fdType='PICT';
  1152.   fndrinfo.fdCreator='MDRW';
  1153.   retcode=setfinfo( pltfilename,0,&fndrinfo);
  1154.   }
  1155. if (plotter == lw){
  1156.   retcode=getfinfo( pltfilename,0,&fndrinfo);
  1157.   fndrinfo.fdType='TEXT';
  1158.   retcode=setfinfo( pltfilename,0,&fndrinfo);
  1159.   }
  1160. #endif
  1161.   exit(0);
  1162. }
  1163.  
  1164. int eof(f)
  1165. FILE *f;
  1166. {
  1167.     register long ch;
  1168.  
  1169.     if (feof(f))
  1170.         return 1;
  1171.     if (f == stdin)
  1172.         return 0;
  1173.     ch = getc(f);
  1174.     if (ch == EOF)
  1175.         return 1;
  1176.     ungetc(ch, f);
  1177.     return 0;
  1178. }
  1179.  
  1180.  
  1181. int eoln(f)
  1182. FILE *f;
  1183. {
  1184.     register long ch;
  1185.  
  1186.     ch = getc(f);
  1187.     if (ch == EOF)
  1188.         return 1;
  1189.     ungetc(ch, f);
  1190.     return (ch == '\n');
  1191. }
  1192.  
  1193.  
  1194. void memerror()
  1195. {
  1196. printf("Error allocating memory\n");
  1197. exit(-1);
  1198. }
  1199.  
  1200. MALLOCRETURN *mymalloc(x)
  1201. long x;
  1202. {
  1203. MALLOCRETURN *mem;
  1204. mem = (MALLOCRETURN *)malloc(x);
  1205. if (!mem)
  1206.   memerror();
  1207. else
  1208.   return (MALLOCRETURN *)mem;
  1209. }
  1210.